package com.kevinkk.dp;

import java.util.Scanner;

/**
 * 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
 * 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
 */

/**
 * 0-1 背包：n 个物品，背包重量为 m，每个物品只有一个
 * 完全背包：n 个物品，背包重量为 m， 每个物品有无限个
 *
 * 解题方法可以分为两种：使用 二维dp数组 或者 使用一维滚动数组
 * 使用一维数组时，需要注意遍历顺序：
 *      首先‼️：只能先遍历物品，然后再遍历背包，这样做的目的是能遍历到全部的物品
 *      其次‼️：遍历背包时，需要倒叙遍历，这样做的目的是确保每个物品只使用一次
 */

public class Knapsack{
    /**
     * 二维 dp 数组
     *
     * 1. dp 数组含义 dp[i][j]：对于物品 i 在背包容量为 j 时背包里的最大价值
     * 2. dp 公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
     *      对于物品 i，要么不放这个物品，那么此时背包容量就是仍然是 j，此时的最大价值和上一个物品时的一样 dp[i-1][j]
     *                要么放置这个物品，此时背包容量需要减去这个物品的重量 j-weight[i]，同样价值是在上一个物品的价值上再加上 value[i]
     * 3. 初始化：
     *      显然，当背包重量为 0 时，最大价值肯定为 0（放不了任何东西） 也就是说 dp[i][0] = 0
     *      对于物品 0 来说，只有当背包重量大于 weight[0] 时，此时背包的最大价值就是物品 0 的价值
     * 4. 遍历顺序：
     *      二维 dp数组，既可以先遍历物品、也可以先遍历背包重量，因为 dp 公式是非常明确的
     */
    public void Solution1(){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        int[] value = new int[m], weight = new int[m];
        for(int i = 0; i < m; i++) weight[i] = sc.nextInt();
        for(int i = 0; i < m; i++) value[i] = sc.nextInt();
        int[][] dp = new int[m][n+1];
        for(int i = weight[0]; i <= n; i++)
            dp[0][i] = value[0];

        for(int i = 1; i < m; i++){
            for(int j = 1; j <= n;j ++){
                if(j >= weight[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[m-1][n]);
    }

    /**
     * 一维滚动 dp 数组
     * 在计算二维数组时，其实 dp[i][j] 的状态是完全依赖于 dp[i-1][j] 的，因此考虑每次直接在 dp[i-1][j] 上计算，将二维数组压缩为一维
     *
     * 1. dp 数组含义：dp[j] 背包容量为 j 时 背包的最大价值
     * 2. dp 公式：dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
     *          不放物品 i 和放了 物品 i 后的最大值
     * 3. 初始化：显然 dp[0] 放不了任何物品，最大价值也为 0
     * 4. 遍历顺序：
     *      首先‼️：只能先遍历物品，然后再遍历背包，这样做的目的是能遍历到全部的物品
     *      其次‼️：遍历背包时，需要倒叙遍历，这样做的目的是确保每个物品只使用一次
     */
    public void Solution2(){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        int[] value = new int[m], weight = new int[m];
        for(int i = 0; i < m; i++) weight[i] = sc.nextInt();
        for(int i = 0; i < m; i++) value[i] = sc.nextInt();
        int[] dp = new int[n+1];

        for(int i = 0; i < m; i++){
            for(int j = n; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }

        System.out.println(dp[n]);
    }
}